package myjava.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javax.crypto.spec.IvParameterSpec;
import javax.swing.text.html.HTMLDocument.Iterator;

public class MaxGap {
	public static int maximumGap(int[] num) {
		
		if(num.length < 2 || num == null) return 0;
		
		int maxNum = num[0];
		int minNum = num[0];
		
		for(int i: num)
		{
			maxNum = Math.max(maxNum, i);
			minNum = Math.min(minNum, i);
		}
		
		int len = (int)Math.ceil((double)(maxNum - minNum)/(num.length - 1));
		
		int[] buckMin = new int[(maxNum - minNum)/len + 1];
		int[] buckMax = new int[(maxNum - minNum)/len + 1];
		
		Arrays.fill(buckMin, Integer.MAX_VALUE);
	    Arrays.fill(buckMax, Integer.MIN_VALUE);
		
		for(int x : num)
		{
			int i = (x-minNum)/len;
			
			
			if(buckMax[i] < x ) buckMax[i] = x;
			if(buckMin[i] > x ) buckMin[i] = x;
		}
        
		int prev = minNum;
		int maxGap = 0;
		for(int i=0;i<buckMin.length -1;i++)
		{
			
			if(buckMin[i] == Integer.MAX_VALUE) continue;
			
			maxGap = Math.max(maxGap, buckMin[i] - prev);
			prev = buckMax[i];
		}
		
		maxGap = Math.max(maxGap, maxNum - prev); 
		return maxGap;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {1,3,6,10,15,21};
		System.out.println(maximumGap(a));
	}

}
